Prior schemes of memory authentication may suffer from inherent read-after-write dependencies between processing of the various levels of the replay protection tree. The cryptography of the replay protection works in such a way that the cryptographic processing of a child node cannot start until the cryptographic processing of the parent node is complete. Consequently, the scheme is very prone to pipeline bubbles, and in the worst case, can end up tripling the memory latency for the protected regions of memory compared to the unprotected regions of memory. Depending on the work load, the added latency can adversely impact the platform's power/performance characteristics significantly.